/**
*   @file quadTreeADT.c
*	Implementacion del QuadTree
*   Fecha de ultima modificacion 06/11/2007.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include "quadTreeADT.h"
#include "../hashADT/hash.h"

/**
*	\var QUAD
* 	Valor entero 4.
*/ 
#define QUAD	4


/**
*	\struct quadCDT
* 	Estructura del header del arbol.
* 	@param freeElement Funcion de liberacion.
* 	@param copyElement Funcion de copia
* 	@param cmpElement Funcion de comparacion.
* 	@param element_size Tamanio de la estrucutra a guardar en el arbol
*/ 
struct quadCDT
{
	struct nodoCDT * 	nodes; 
	fnFree				freeElement;
	fnCpyCmp			copyElement;
	fnCpyCmp			cmpElement;
	int					element_size;
};

/**
*	\struct nodoCDT
* 	Estructura del nodo del arbol.
* 	@param color Puntero al elemento a guardar en el arbol.
* 	@param childcount Cantidad de hijos.
* 	@param childs[4] Vector con punteros a los 4 hijos del arbol.
*/ 
typedef struct nodoCDT
{
	ElementT			color;
	int					childcount;
	struct nodoCDT * 	childs[4];
}nodeCDT;

static int chkColor(quadADT qtree, char * quadcode, nodeCDT * actual);
static void freeQuad( nodeCDT * node, fnFree freeElement );
static int  Precondition(void * condicion);
static nodeCDT * insertQNode(nodeCDT * node, char * quadcode, fnCpyCmp cpyElement, ElementT color);
static nodeCDT * FindPossibleNode( nodeCDT * raiz, char * quadcode );
static void swapQNodes(nodeCDT * node, pole coord1, pole coord2);



static void rotateQNodes( nodeCDT * node, int orientation);
static void swapRotate(nodeCDT * node, int clockside);
static void hashData(hashADT hashtable, nodeCDT * node, int totalpixels);


quadADT 
NewQuad(int elementSize, fnFree freeElement, fnCpyCmp copyElement, fnCpyCmp cmpElement)
{
	quadADT auxtree;
	int i;
	
	if (!Precondition(freeElement) || !Precondition(copyElement) || 
		!Precondition(freeElement) || elementSize <= 0)
		return NULL;
	
	if ( (auxtree = malloc(sizeof(struct quadCDT))) == NULL )
		return NULL;
		
/* Crea la raiz del quadTree */
		
	if ( (auxtree -> nodes = malloc(sizeof(struct nodoCDT))) == NULL )
	{
		free(auxtree);
		return NULL;
	}
	
/* 	Inicializa la raiz del quadTree y el header */
		
	auxtree -> nodes -> childcount = 0;
	auxtree -> nodes -> color = NULL;
	auxtree -> element_size = elementSize;
	auxtree -> freeElement = freeElement;
	auxtree -> copyElement = copyElement;
	auxtree -> cmpElement = cmpElement;
	
	for (i = 0 ; i < QUAD ; i++)
		auxtree -> nodes -> childs[i] = NULL;
	
	return auxtree;	
}

int
insertLeaf(quadADT qtree, char * quadcode, ElementT color)
{
	nodeCDT * auxdad;
	
	if (!Precondition(qtree) || !Precondition(quadcode) || !Precondition(color))
		return 0;
	
	if ((auxdad = insertQNode(qtree -> nodes, quadcode, qtree -> copyElement, color)) == NULL)
	{
		freeQtree(qtree);
		return 0;
	}
		
	if (auxdad -> childcount == 4)
		if (chkColor(qtree, quadcode, qtree -> nodes) == -1)
		{
			freeQtree(qtree);
			return 0;
		}
		
	return 1;
}

ElementT
getElement(quadADT qtree, char * quadcode)
{
	nodeCDT * node;
	
	if( ( node = FindPossibleNode( qtree -> nodes, quadcode ) ) == NULL )
		return NULL;
		
	return node -> color;
}

int
swapQPoles(quadADT qtree, pole fpole, pole spole)
{
	int orientation;
	pole coord1, coord2;
	
	orientation = fpole + spole;
	
	if(orientation != 1 && orientation != 5)
	{
		printf("Wrong criteria for node swaping, must be North-South or East-West \n");
		return 0;
	}
	
	if(orientation == 1)
	{
		coord1 = E;
		coord2 = S;
	}
	else
	{
		coord1 = S;
		coord2 = E;
	}
	
	swapQNodes(qtree -> nodes, coord1, coord2);
	
	return 1;
}

/* funcion wrapper utilizada por imageADT */

int 
rotateQPoles( quadADT qtree, int orientation )
{
	
/* Chequea que la orientacion elegida sea la correcta */
	
	if (orientation != 1 && orientation != 0)
	{
		printf("Error, second argument must be either 0 or 1 \n");
		return 0;
	}
	
	rotateQNodes( qtree->nodes, orientation);
	
	return 1;
}

int
changeColor( quadADT qtree, char * quadcode, ElementT newColor )
{
	nodeCDT * aux; 

	if( ( aux = FindPossibleNode( qtree->nodes, quadcode ) ) == NULL )
		return 0; /*no encontre el nodo*/ 

	qtree->copyElement( aux->color, newColor ); 
	
	return 1;
}

int 
hashLeafs(hashADT hashtable, quadADT qtree, int totalpixels)
{
	
	if (!Precondition(hashtable) || !Precondition(qtree) || !Precondition(qtree -> nodes) || totalpixels <= 0)
		return 0;
		
	hashData(hashtable, qtree -> nodes, totalpixels);
	
		
	return 1;
}

void 
freeQtree( quadADT qtree )
{
	if (!Precondition(qtree))
		return;
	
	freeQuad( qtree -> nodes, qtree->freeElement );
	free(qtree);

	qtree = NULL;


	return;
}


static int
Precondition(void * condicion)
{
	if (condicion == NULL)
		return 0;
		
	return 1;
}

static void
hashData(hashADT hashtable, nodeCDT * node, int quadraticSize)
{
	int i, isSon = 0;
	
	if(!Precondition(node))
		return;
	
	for (i = 0 ; i < QUAD ; i++)
		if (node -> childs[i] == NULL)
			isSon += 1;
			
	if (isSon == 4)
	{
		insertKey(hashtable, node -> color, quadraticSize);
		return;
	}
	
	for (i = 0 ; i < QUAD ; i++)
		if (node -> childs[i] != NULL)
				hashData(hashtable, node -> childs[i], quadraticSize / 4);
			
	return;
}

static nodeCDT *
insertQNode(nodeCDT * node, char * quadcode, fnCpyCmp cpyElement, ElementT color)
{

	nodeCDT * auxnode;
	int i;

	if (*(quadcode + 1) == '\0')	
	{
		/* Si la hoja que se quiere insertar ya existe, entonces es un pixel repetido y por lo tanto
		 * hay un error.
 		*/ 
 
		if (node -> childs[(int)*quadcode - '0'] != NULL)
			return NULL;
			
		/* Si la hoja no existe, se aloca el espacio para la hoja y el elemento de la misma */
	
		
		if ( (auxnode = malloc(sizeof(struct nodoCDT))) == NULL)
		{
			printf("Not enough memory to create leaf \n");
			return NULL;
		}
			
		if ( (auxnode -> color = malloc(sizeof(color))) == NULL)
		{
			printf("Not enough memory to create pixel \n");
			return NULL;
		}
			
		/* Se copia el pixel(color) al elemento de la hoja */
			
			cpyElement(auxnode -> color, color);
			auxnode -> childcount = 0;
			
			for (i = 0 ; i < QUAD ; i++)
				auxnode -> childs[i] = NULL;
			
			node -> childs[(int)*quadcode - '0'] = auxnode;
			node -> childcount++;
			
			return node;
	}
	
	/* Crea los nodos intermedios si es necesario */
	
	if (node -> childs[(int)*quadcode - '0'] == NULL)
	{
		if ( (auxnode = malloc(sizeof(struct nodoCDT))) == NULL)
		{
			printf("Not enough memory to create node \n");
			return NULL;
		}
		auxnode -> color = NULL;
		auxnode -> childcount = 0;	/* Al crear el nodo, no tiene hijos */
		
		for (i = 0 ; i < QUAD ; i++)
			auxnode -> childs[i] = NULL;
			
		node -> childs[(int)*quadcode - '0'] = auxnode;
		node -> childcount++;
	}
	
	return insertQNode(node -> childs[(int)*quadcode - '0'], quadcode + 1, cpyElement, color);
}


static nodeCDT * 
FindPossibleNode( nodeCDT * raiz, char * quadcode )
{
	if( raiz == NULL )
		return NULL;
		
	else if( raiz->childs[(int)quadcode[0] - '0'] == NULL )
		return raiz;
	
	else if( *(quadcode+1) == 0 )
		return raiz->childs[(int)quadcode[0] - '0'];
	
	return FindPossibleNode( raiz->childs[(int)quadcode[0] - '0'], quadcode+1);			
}

static int 
chkColor(quadADT qtree, char * quadcode, nodeCDT * actual )
{	
	if (*(quadcode) == '\0')
		return 1;
		
/* Si devuelve 1, se tiene que seguir chequeando si los 4 pixeles son iguales */
		
	if( chkColor(qtree, quadcode + 1, actual -> childs[(int)*quadcode - '0']) == 1 )
	{
		int i, flag = 0;
		
		if (actual -> childcount != 4)
			return 0;
		
		/* Comparacion de los 4 pixeles */
		
		for (i = 1 ; i < QUAD ; i++)
			flag += qtree -> cmpElement(actual -> childs[0] -> color, actual -> childs[i] -> color);
			
		if( flag != 3 )
			return 0;
			
		/* los 4 hijos son del mismo color */
		
		if( ( actual -> color = malloc( qtree -> element_size ) ) == NULL )
			return -1; /*error en memoria*/
			
		qtree -> copyElement( actual -> color, actual -> childs[0] -> color );
		
		/* Libera el pixel de cada hoja, luego libera las hojas y ahora el padre 
		 * tiene hijos NULL 
		 */
		
		for (i = 0 ; i < QUAD ; i++)
		{
			qtree -> freeElement(actual -> childs[i] -> color);
			actual -> childs[i] -> color = NULL;
			free(actual->childs[i]);
			actual -> childs[i] = NULL;
		}
		
		/*El nodo ahora pasa a ser una hoja, no tiene hijos*/
		actual -> childcount = 0;
		return 1;
	}
	return 0;
}

static void
swapQNodes(nodeCDT * node, pole coord1, pole coord2)
{
	if (node == NULL)
		return;
	
	
	if (node -> childcount == 0)
		return;
	
	nodeCDT * auxi;
	int i;
	
	auxi = node -> childs[0];
	node -> childs[0] = node -> childs[coord1];
	node -> childs[coord1] = auxi;
	auxi = node -> childs[3];
	node -> childs[3] = node -> childs[coord2];
	node -> childs[coord2] = auxi;
	
	for (i = 0 ; i < QUAD ; i++)
		swapQNodes(node -> childs[i], coord1, coord2);
		
	return;		
}

/* orientation == 0 rota a la derecha, orientation == 1 rota a la izquierda
 * recorre el quadTree completo recursivamente rotando los nodos.
 */ 

static void 
rotateQNodes(nodeCDT * node, int orientation)
{
	int i;
	
	if (node == NULL)
		return;
		
	if (node -> childcount == 0)
		return;
		
	swapRotate(node, orientation);
	
	for (i = 0 ; i < QUAD ; i++)
		rotateQNodes(node -> childs[i], orientation);

	return;
}

/* Rota los nodos de un mismo nivel y padre antihorario u horario segun "clockwise" */

static void 
swapRotate( nodeCDT * node, int clockside)
{
	nodeCDT * aux; 
	int nodepole1, nodepole2;
	
	if (clockside == 1)
	{	
		nodepole1 = 2;
		nodepole2 = 1;
	}
	else
	{
		nodepole1 = 1;
		nodepole2 = 2;
	}
	
	aux = node->childs[0];
	node -> childs[0] = node -> childs[nodepole1];
	node -> childs[nodepole1] = node -> childs[3];
	node -> childs[3] = node -> childs[nodepole2];
	node -> childs[nodepole2] = aux;
} 

static void
freeQuad( nodeCDT * node, fnFree freeElement )
{
	int i;
	
	/*si es un nodo tengo que revisar a los 4 hijos, pero si es una hoja el childcount es 0
	 * entonces salgo del ciclo de una, libero el color, libero la hoja*/
	for( i=0 ; i < QUAD && node -> childcount != 0 ; i++ )
	{
		if( node -> childs[i] != NULL )
		{
			freeQuad( node -> childs[i], freeElement );
			node -> childcount--;
		}
	}
		
	freeElement(node->color);
	free(node);
	
	return;
}
